package com.algorithm;


import com.algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import static com.algorithm.model.TreeNodeService.getTree;

public class BinaryTree {

    static List<Integer> list = new LinkedList<>();

    public static void main(String[] args) {

        TreeNode rootNode = getTree();
        preorder(rootNode);
        print();
        list = new ArrayList<>();
        inorder(rootNode);
        print();
        list = new ArrayList<>();
        postorder(rootNode);
        print();
//        list = new ArrayList<>();
//        rightInorder(rootNode);
//        print();
//        System.out.println("=========");
//        list = new ArrayList<>();
//        order(rootNode);
//        print();

    }

    public static void print() {
        for (int i : list) {
            System.out.print(i + ",");
        }
        System.out.print("\b");
        System.out.println();
    }

    static void preorderWhile(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(rootNode);
        TreeNode tmp;
        while (!stack.empty()) {

            tmp = stack.pop();

            list.add(tmp.val);

            if (tmp.right != null) {
                stack.add(tmp.right);
            }

            if (tmp.left != null) {
                stack.add(tmp.left);
            }

        }

    }


    static void inorderWhile(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tmp = rootNode;

        while (tmp != null || !stack.isEmpty()) {

            while (tmp != null) {
                stack.add(tmp);
                tmp = tmp.left;
            }

            tmp = stack.pop();

            list.add(tmp.val);

            if (tmp.right != null) {
                tmp = tmp.right;
            } else {
                tmp = null;
            }

        }


    }

    static void postorderWhile(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(rootNode);
        TreeNode tmp;
        while (!stack.empty()) {

            tmp = stack.pop();

            list.add(tmp.val);

            if (tmp.left != null) {
                stack.add(tmp.left);
            }
            if (tmp.right != null) {
                stack.add(tmp.right);
            }

        }

    }

    static void order(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        order(rootNode.left);
        order(rootNode.right);
        list.add(rootNode.val);

    }

    public static void preorder(TreeNode rootNode) {

        list.add(rootNode.val);

        if (rootNode.left != null) {
            preorder(rootNode.left);
        }

        if (rootNode.right != null) {
            preorder(rootNode.right);
        }


    }

    public static void inorder(TreeNode rootNode) {


        if (rootNode.left != null) {
            inorder(rootNode.left);
        }

        list.add(rootNode.val);

        if (rootNode.right != null) {
            inorder(rootNode.right);
        }

    }

    public static void postorder(TreeNode rootNode) {

        if (rootNode.left != null) {
            postorder(rootNode.left);
        }
        if (rootNode.right != null) {
            postorder(rootNode.right);
        }
        list.add(rootNode.val);

    }

    public static void rightInorder(TreeNode rootNode) {

        if (rootNode.right != null) {
            rightInorder(rootNode.right);
        }
        list.add(rootNode.val);

        if (rootNode.left != null) {
            rightInorder(rootNode.left);
        }

    }






}
